[MPRI 2.11.1] Algorithmes avancés 2014.10.16 Cours n°3(A/C)

Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel
Cours n°3 - Partie A/C [16/10/2014]
PTAS: Schémas d'Approximation Polynomial
• Le voyageur de commerce euclidien (Euclidean TSP)

Exercise session 3 (to return on 23/10/2014)
• A Fully Polynomial Time Approximation Scheme for the Knapsack problem
• A Constant Time Approximation Scheme for Maximal Matching Size in undirected constant degree graphs